package Midium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution15_2 {
    // 暴力超时
    public static void main(String[] args) {
        threeSum(new int[]{1,2,-2,-1});
    }

    public static List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ans = new ArrayList();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length-2 ; i++){
            if(i > 0 && nums[i] == nums[i-1]) // 防止找重复的当前数，下同
                continue;
            int a = (-1)*nums[i];
            if(a < 0) break; //如果第一个数比0大，说明已经找完了
            for(int j = i+1; j < nums.length -1 ; j++){
                if(j>i+1 && nums[j]==nums[j-1])
                    continue;
                int b = nums[j];
                int k = nums.length-1;
                int c = nums[k];
                while(a!=b+c && k>j+1){
                    c = nums[--k];
                }
                if(a == b+c){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add((-1)*a);
                    list.add(b);
                    list.add(c);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    public static List<List<Integer>> threeSum_timeOut(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> curList = new ArrayList<Integer>();
        Arrays.sort(nums);

        dfs(nums,0,ans,curList);
        return ans;
    }
    public static void dfs(int[] nums,int cur,List<List<Integer>> ans , List<Integer> curList){
        if(curList.size() == 3){
            if(!ans.isEmpty()){
                for(List<Integer> temp : ans){
                    if(temp.get(0)==curList.get(0) && temp.get(1)==curList.get(1) && temp.get(2)==curList.get(2))
                        return;
                }
            }
            if(curList.get(0)+curList.get(1)+curList.get(2) == 0){
                ans.add(new ArrayList(curList));
            }
            return;
        }
        for(int i = cur ; i < nums.length ; i++){
            curList.add(nums[i]);
            dfs(nums,i+1,ans,curList);
            curList.remove((Integer)nums[i]);
        }
    }
}
